1808D - Petya Petya Petr and Palindromes - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const int linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};


// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 2e5+10;
int n, k, ans, arr[N], mp[N];

void sol() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    vi temp;
    int x = k+1;
    for (int i = 1; i <= n-k+1; i++) temp.pb(x), x += 2;

    auto getLow = [&](int idx) {
        int i = 0, j = temp.size()-1, ans = 0;
        while (i <= j) {
            int mid =(i+j)/2;
            int x = temp[mid]; int inv = x-idx;
            if (idx <= inv) j = mid-1, ans = mid;
            else i = mid+1;
        }
        return /*temp[ans]-idx*/ans;
    };
    
    map<int, int> mp;
    int l = k-1, h = k+1, cnt = 2;
    mp[arr[l]]++; mp[arr[h]]++;
    for (int i = 2; i <= (n-(k/2)); i += 2) {
        int low = (i-(k/2) <= 0?(k-i+1):i);
        int temp = n-(i-(n-k+1));
        int high = (i+2*(k/2)>n?temp:i+2*(k/2));

        while (l-2 >= low) {
            l -= 2;
            mp[arr[l]]++;
            cnt++;
        }
        while (l+2 <= low) {
            mp[arr[l]]--;
            l += 2;
            cnt--;
        }
        while (h+2 <= high) {
            h += 2;
            mp[arr[h]]++;
            cnt++;
        }
        while (h-2 >= high) {
            mp[arr[h]]--;
            h -= 2;
            cnt--;
        }

        ans += (cnt-mp[arr[i]]);
    }

    mp.clear(); 
    l = k, h = k, cnt = 1;
    mp[arr[l]]++;
    
    for (int i = 1; i <= (n-(k/2)); i += 2) {
        int low = (i-(k/2)<=0?(k-i+1):i);
        int temp = n-(i-(n-k+1));
        int high = (i+2*(k/2)>n?temp:i+2*(k/2));

        while (l-2 >= low) {
            l -= 2;
            mp[arr[l]]++;
            cnt++;
        }
        while (l+2 <= low) {
            mp[arr[l]]--;
            l += 2;
            cnt--;
        }
        while (h+2 <= high) {
            h += 2;
            mp[arr[h]]++;
            cnt++;
        }
        while (h-2 >= high) {
            mp[arr[h]]--;
            h -= 2;
            cnt--;
        }

        ans += (cnt-mp[arr[i]]);
    }

    cout << ans << endl;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}